package middle;

import java.util.*;

/**
 * 给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
 *
 * 图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class CloneGraph {
    /**
     * DFS
     * */
    class Solution {
        // 使用map来保存已经访问过的结点 映射关系为 旧结点-拷贝的新结点
        Map<Node, Node> hashMap = new HashMap<>();
        public Node cloneGraph(Node node) {
            if(Objects.isNull(node)){
                return null;
            }
            return recur(node);
        }

        Node recur(Node node){
            // 已经访问过的
            if(hashMap.containsKey(node)){
                return hashMap.get(node);
            }
            Node newNode = new Node(node.val);
            hashMap.put(node, newNode);
            for (Node n : node.neighbors){
                newNode.neighbors.add(recur(n));
            }
            return newNode;
        }
    }

    /**
     * BFS
     * */
    class Solution1{

        public Node cloneGraph(Node node) {
            if(Objects.isNull(node)){
                return null;
            }
            // 使用map来保存已经访问过的结点 映射关系为 旧结点-拷贝的新结点
            Map<Node, Node> hashMap = new HashMap<>();
            Deque<Node> deque = new LinkedList<>();
            deque.push(node);
            hashMap.put(node, new Node(node.val));
            while(!deque.isEmpty()){
                Node curNode = deque.poll();
                // 邻居结点
                for (Node n : curNode.neighbors){
                    if(!hashMap.containsKey(n)){
                        deque.offer(n);
                        hashMap.put(n, new Node(n.val));
                    }
                    hashMap.get(curNode).neighbors.add(hashMap.get(n));
                }
            }
            return hashMap.get(node);
        }
    }
}

class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
